Route planning algorithms (such as the Dijkstra method, A* method or Moore/Pape methods) are known. However, these can be somewhat slow. An example of how the speed of such route planning may be increased is shown in U.S. Pat. No. 6,636,800, the teaching of which are hereby incorporated by reference. U.S. Pat. No. 6,636,800 teaches pre-processing of map data by dividing the map into regions and determining a tree of shortest paths (minimum cost paths) to each region of the map. This pre-processed data is stored in memory and used during the calculation of a route.
More specifically, when an origin lies within one region and a destination lies within another region, the pre-determined tree of shortest paths can be used to quickly determine the path between the regions to be used as part of the route. Such a method reduces the level of processing required to determine a route because it reduces the number of paths explored from when a user requests determination of a route.
It will be understood that “shortest” path does not necessarily mean the path of shortest distance but means the path having the minimum cost. The cost of path will depend on the factors being considered as specified in a cost formula and may take into account factors such as quickest route and fuel usage.
Such a method is very successful when the shortest paths between regions remain static. However, changes in traffic conditions over time can change the path that is the shortest path between regions such that the pre-processed tree no longer identifies the true shortest paths between regions. This can result in a route being determined that is not the optimum route for specified criteria.